package com.chenken;

/**
 * 选择排序
 *	从序列中找出最大元素，与末尾元素交换位置
	执行完一轮之后，末尾的元素就是最大的元素
	执行下一轮的时候，忽略之前找到的元素
	选择排序的交换次数要远远少于冒泡排序，平均性能优于冒泡排序
	最好，最坏的时间复杂度都是O(n^2),
	空间复杂度O(1)
 */
public class SelectionSort<T extends Comparable<T>> extends Sort<T>{

	@Override
	protected void sort() {
		for(int end = arrays.length-1;end>0;end--) {
			int maxIndex = 0;
			for(int begin = 1;begin<=end;begin++) {
				if(compare(arrays[maxIndex],arrays[begin])<=0) {
					maxIndex = begin;
				}
			}
			swap(end,maxIndex);
		}
	}
	
}
